package leetcode.f1t100;

/**
 * 最短窗口子串
 * https://leetcode.com/problems/minimum-window-substring/
 *
 * @Author lichongxiao
 * @Date 2022/11/28 9:24
 */
public class Q76_MinimumWindowSubstring {

    public static void main(String[] args) {
        Q76_MinimumWindowSubstring bean = new Q76_MinimumWindowSubstring();
        System.out.println(bean.minWindow("ABDDCDBA","ABC"));
        System.out.println(bean.minWindowL("ABDDCDBA","ABC"));
    }

    public String minWindow(String s, String t) {
        int slen = s.length(), tlen = t.length(), left = 0, right = 0, ansLeft = -2 - slen, ansRight = -1;
        int[] counts = new int['z' - 'A' + 1];
        for (int i = 0; i < tlen; i++) {
            counts[t.charAt(i) - 'A']++;
        }

        for (int i = 0, l = counts.length; i < l; i++) {
            if (counts[i] == 0) {
                counts[i] = -slen;
            }
        }

        while (left <= right && right < slen) {
            counts[s.charAt(right) - 'A']--;
            while (isAns(counts)) {
                if(ansRight - ansLeft > right - left){
                    ansRight = right;
                    ansLeft = left;
                }
                counts[s.charAt(left)-'A']++;
                left++;
            }
            right++;
        }
        return ansLeft < 0 ? "" : s.substring(ansLeft,ansRight+1);
    }

    public String minWindowL(String s, String t) {
        int [] map = new int[128];
        for (char c : t.toCharArray()) {
            map[c]++;
        }
        int start = 0, end = 0, minStart = 0, minLen = Integer.MAX_VALUE, counter = t.length();
        while (end < s.length()) {
            final char c1 = s.charAt(end);
            if (map[c1] > 0) counter--;
            map[c1]--;
            end++;
            while (counter == 0) {
                if (minLen > end - start) {
                    minLen = end - start;
                    minStart = start;
                }
                final char c2 = s.charAt(start);
                map[c2]++;
                if (map[c2] > 0) counter++;
                start++;
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
    }

    private boolean isAns(int[] counts) {
        boolean ans = true;
        for (int count : counts) {
            ans &= (count <= 0);
        }
        return ans;
    }

}
